package com.cuz.daileetcode.bat100;

public class 每行每列有序二位数组找第k小 {


    static class Info {
        int mostNear;
        int numLessEqualCount;

        public Info(int mostNear, int numLessEqualCount) {
            this.mostNear = mostNear;
            this.numLessEqualCount = numLessEqualCount;
        }
    }

    private static Info findLessEqualTarget(int[][] arr, int target) {
        //最多行
        // 和列
        int rowMax = arr.length;
        int colMax = arr[0].length;
        //开始行 和列
        int x = 0;
        int y = colMax - 1;
        //最近target的数
        int mostNear = Integer.MIN_VALUE;
        //小于等于target的数的数量
        int numLessEqualCount = 0;
        //遍历
        while (x < rowMax && y >= 0) {
            //如果当前位置的数 大于了 target 那么向左移动
            if (arr[x][y] > target) {
                y--;
            } else {
                //如果当前数 小于等于target
                //更新最接近target的数
                mostNear = Math.max(mostNear, arr[x][y]);
                //小于等于target的数 ————当前行的所有左侧数 包括自己==》y+1
                numLessEqualCount += y + 1;
                //向下移动
                x++;
            }
        }
        return new Info(mostNear, numLessEqualCount);
    }


    public static int findKMinIn(int[][] arr, int k) {
        int rowMax = arr.length;
        int colMax = arr[0].length;
        int mostMin = arr[0][0] - 1;
        int mostMax = arr[rowMax - 1][colMax - 1] + 1;
        int ans = 0;
        while (mostMin + 1 != mostMax) {
            int mid = ((mostMax - mostMin) >> 1) + mostMin;
            Info info = findLessEqualTarget(arr, mid);
            int count = info.numLessEqualCount;
            //小于当前mid数的个数 小于k 说明mid笑了 mostMid=mid 向右侧二分
            if (count < k) {
                mostMin = mid;
            } else if (count == k) {
                return info.mostNear;
            } else {
                //小于当前mid数的个数 大于k 说明mid大了
                // mostMax = mid 向左侧二分
                mostMax = mid;
                ans = info.mostNear;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[][] ints = {
                {1, 2, 3, 4},
                {2, 3, 4, 5},
                {5, 6, 7, 8},
        };
        Info lessEqualTarget = findLessEqualTarget(ints, 5);
        System.out.println(findKMinIn(ints, 8));
        System.out.println(lessEqualTarget);
    }
}
